package bfs;

import java.util.*;

/**
 * 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
 * 锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
 * 列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
 * 字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
 *
 * 限制
 * 1 <= deadends.length <= 500
 * deadends[i].length == 4
 * target.length == 4
 * target 不在 deadends 之中
 * target 和 deadends[i] 仅由若干位数字组成
 */
public class OpenTheLock_752 {
    public int openLock(String[] deadends, String target) {
        // 队列记录bfs每一层穷举的密码
        Queue<String> q = new LinkedList<>();
        // 记录已经穷举过的密码，即进入队列了的密码
        Set<String> visited = new HashSet<>();

        // 记录需要跳过的死亡密码
        // deads.addAll(Arrays.asList(deadends));
        Set<String> deads = new HashSet<>(Arrays.asList(deadends));

        int step = 0;
        q.offer("0000");
        visited.add("0000");
        while (!q.isEmpty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                String passwd = q.poll();
                if (passwd.equals(target)) {
                    return step;
                }
                if (deads.contains(passwd)) {
                    continue;
                }

                for (int j = 0; j < 4; j++) {
                    String minus = minusOne(passwd, j);
                    if (!visited.contains(minus)) {
                        q.offer(minus);
                        visited.add(minus);
                    }
                    String plus = plusOne(passwd, j);
                    if (!visited.contains(plus)) {
                        q.offer(plus);
                        visited.add(plus);
                    }

                }
            }
            step++;
        }
        // 穷举完都找不到就返回-1
        return -1;
    }

    // 第i位向上拨动一位
    public String plusOne(String s, int i) {
        char[] chars = s.toCharArray();
        if (chars[i] == '9') {
            chars[i] = '0';
        } else {
            chars[i] += 1;
        }
        return new String(chars);
    }

    // 第i位向下拨动一位
    public String minusOne(String s, int i) {
        char[] chars = s.toCharArray();
        if (chars[i] == '0') {
            chars[i] = '9';
        } else {
            chars[i] -= 1;
        }
        return new String(chars);
    }
}
